Linked List

A comprehensive guide to linked list algorithms and techniques for Data Structures and Algorithms.

Table of Contents

1. Basic Node Structures
2. Basic Linked List Operations
3. Two Pointer Techniques
4. Reversal Techniques
5. Merge and Sorting Techniques
6. Intersection and Comparison
7. Advanced Techniques
8. Doubly Linked List Operations
9. Usage Examples

---

Basic Node Structures

The foundation of linked list operations starts with node definitions:

Singly Linked List Node

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

Doubly Linked List Node

class DoublyListNode {
    constructor(val = 0, prev = null, next = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

Helper Functions

// Create linked list from array
function createLinkedList(arr) {
    if (!arr || arr.length === 0) return null;

    const head = new ListNode(arr[0]);
    let current = head;

    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }

    return head;
}

// Print linked list for visualization
function printList(head) {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result.join(' -> ');
}

---

Basic Linked List Operations

1. Traversal

function traverseList(head) {
    const values = [];
    let current = head;

    while (current) {
        values.push(current.val);
        current = current.next;
    }

    return values;
}

Time Complexity: O(n) | Space Complexity: O(1)

2. Search

function searchList(head, target) {
    let current = head;
    let position = 0;

    while (current) {
        if (current.val === target) {
            return position;
        }
        current = current.next;
        position++;
    }

    return -1; // Not found
}

Time Complexity: O(n) | Space Complexity: O(1)

3. Insert Operations

Insert at Beginning

function insertAtBeginning(head, val) {
    const newNode = new ListNode(val);
    newNode.next = head;
    return newNode;
}

Time Complexity: O(1)

Insert at End

function insertAtEnd(head, val) {
    const newNode = new ListNode(val);

    if (!head) return newNode;

    let current = head;
    while (current.next) {
        current = current.next;
    }

    current.next = newNode;
    return head;
}

Time Complexity: O(n)

Insert at Specific Position

function insertAtPosition(head, val, position) {
    if (position === 0) return insertAtBeginning(head, val);

    const newNode = new ListNode(val);
    let current = head;

    for (let i = 0; i < position - 1 && current; i++) {
        current = current.next;
    }

    if (!current) return head; // Position out of bounds

    newNode.next = current.next;
    current.next = newNode;
    return head;
}

4. Delete Operations

Delete First Occurrence of Value

function deleteValue(head, val) {
    if (!head) return null;

    if (head.val === val) {
        return head.next;
    }

    let current = head;
    while (current.next && current.next.val !== val) {
        current = current.next;
    }

    if (current.next) {
        current.next = current.next.next;
    }

    return head;
}

Delete at Specific Position

function deleteAtPosition(head, position) {
    if (!head || position < 0) return head;

    if (position === 0) {
        return head.next;
    }

    let current = head;
    for (let i = 0; i < position - 1 && current.next; i++) {
        current = current.next;
    }

    if (current.next) {
        current.next = current.next.next;
    }

    return head;
}

---

Two Pointer Techniques

The two-pointer technique is essential for many linked list problems and provides elegant solutions.

1. Find Middle of Linked List

Floyd's Tortoise and Hare Algorithm:

function findMiddle(head) {
    if (!head) return null;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

Time Complexity: O(n) | Space Complexity: O(1)

2. Detect Cycle (Floyd's Cycle Detection)

function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            return true;
        }
    }

    return false;
}

💡 Pro Tip: This is also known as the "Tortoise and Hare" algorithm!

3. Find Cycle Start Node

function detectCycleStart(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            break;
        }
    }

    if (!fast || !fast.next) return null;

    // Find start of cycle
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

4. Find Nth Node from End

Gap Method:

function nthFromEnd(head, n) {
    let first = head;
    let second = head;

    // Move first pointer n steps ahead
    for (let i = 0; i < n; i++) {
        if (!first) return null;
        first = first.next;
    }

    // Move both pointers until first reaches end
    while (first) {
        first = first.next;
        second = second.next;
    }

    return second;
}

5. Remove Nth Node from End

function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;

    let first = dummy;
    let second = dummy;

    // Move first pointer n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        first = first.next;
    }

    // Move both pointers until first reaches end
    while (first) {
        first = first.next;
        second = second.next;
    }

    // Remove the nth node
    second.next = second.next.next;

    return dummy.next;
}

🔧 Technique: Using a dummy node simplifies edge cases!

---

Reversal Techniques

1. Reverse Entire Linked List

Iterative Approach:

function reverseList(head) {
    let prev = null;
    let current = head;

    while (current) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }

    return prev;
}

Time Complexity: O(n) | Space Complexity: O(1)

2. Reverse List Recursively

function reverseListRecursive(head) {
    if (!head || !head.next) return head;

    const newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;

    return newHead;
}

Time Complexity: O(n) | Space Complexity: O(n) due to recursion stack

3. Reverse Between Two Positions

function reverseBetween(head, left, right) {
    if (!head || left === right) return head;

    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;

    // Move to position before left
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }

    let current = prev.next;

    // Reverse the sublist
    for (let i = 0; i < right - left; i++) {
        const nextTemp = current.next;
        current.next = nextTemp.next;
        nextTemp.next = prev.next;
        prev.next = nextTemp;
    }

    return dummy.next;
}

4. Reverse in K Groups

function reverseKGroup(head, k) {
    if (!head || k === 1) return head;

    // Check if we have k nodes
    let count = 0;
    let node = head;
    while (node && count < k) {
        node = node.next;
        count++;
    }

    if (count === k) {
        // Reverse current k nodes
        node = reverseKGroup(node, k);

        while (count > 0) {
            const temp = head.next;
            head.next = node;
            node = head;
            head = temp;
            count--;
        }

        head = node;
    }

    return head;
}

---

Merge and Sorting Techniques

1. Merge Two Sorted Lists

function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(0);
    let current = dummy;

    while (list1 && list2) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }

    current.next = list1 || list2;

    return dummy.next;
}

Time Complexity: O(n + m) | Space Complexity: O(1)

2. Merge K Sorted Lists

Divide and Conquer Approach:

function mergeKLists(lists) {
    if (!lists || lists.length === 0) return null;
    if (lists.length === 1) return lists[0];

    while (lists.length > 1) {
        const mergedLists = [];

        for (let i = 0; i < lists.length; i += 2) {
            const list1 = lists[i];
            const list2 = i + 1 < lists.length ? lists[i + 1] : null;
            mergedLists.push(mergeTwoLists(list1, list2));
        }

        lists = mergedLists;
    }

    return lists[0];
}

Time Complexity: O(n log k) where k is number of lists

3. Merge Sort for Linked List

function sortList(head) {
    if (!head || !head.next) return head;

    // Find middle and split
    const middle = findMiddle(head);
    const rightHalf = middle.next;
    middle.next = null;

    // Recursively sort both halves
    const left = sortList(head);
    const right = sortList(rightHalf);

    // Merge sorted halves
    return mergeTwoLists(left, right);
}

Time Complexity: O(n log n) | Space Complexity: O(log n)

---

Intersection and Comparison

1. Find Intersection of Two Lists

function getIntersectionNode(headA, headB) {
    if (!headA || !headB) return null;

    let pA = headA;
    let pB = headB;

    while (pA !== pB) {
        pA = pA ? pA.next : headB;
        pB = pB ? pB.next : headA;
    }

    return pA;
}

🧠 Algorithm Insight: Each pointer traverses both lists, ensuring they meet at intersection or null!

2. Check if Two Lists are Equal

function areListsEqual(head1, head2) {
    while (head1 && head2) {
        if (head1.val !== head2.val) {
            return false;
        }
        head1 = head1.next;
        head2 = head2.next;
    }

    return !head1 && !head2;
}

---

Advanced Techniques

1. Partition List

Split list around pivot value:

function partition(head, x) {
    const beforeHead = new ListNode(0);
    const afterHead = new ListNode(0);
    let before = beforeHead;
    let after = afterHead;

    while (head) {
        if (head.val < x) {
            before.next = head;
            before = before.next;
        } else {
            after.next = head;
            after = after.next;
        }
        head = head.next;
    }

    after.next = null;
    before.next = afterHead.next;

    return beforeHead.next;
}

2. Rotate List

function rotateRight(head, k) {
    if (!head || !head.next || k === 0) return head;

    // Find length and make it circular
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }
    tail.next = head;

    // Find new tail and head
    k = k % length;
    const stepsToNewTail = length - k;
    let newTail = head;

    for (let i = 1; i < stepsToNewTail; i++) {
        newTail = newTail.next;
    }

    const newHead = newTail.next;
    newTail.next = null;

    return newHead;
}

3. Add Two Numbers

Numbers represented as linked lists:

function addTwoNumbers(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const sum = val1 + val2 + carry;

        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }

    return dummy.next;
}

4. Copy List with Random Pointer

class RandomListNode {
    constructor(val, next = null, random = null) {
        this.val = val;
        this.next = next;
        this.random = random;
    }
}

function copyRandomList(head) {
    if (!head) return null;

    const map = new Map();

    // First pass: create nodes
    let current = head;
    while (current) {
        map.set(current, new RandomListNode(current.val));
        current = current.next;
    }

    // Second pass: set pointers
    current = head;
    while (current) {
        const newNode = map.get(current);
        newNode.next = current.next ? map.get(current.next) : null;
        newNode.random = current.random ? map.get(current.random) : null;
        current = current.next;
    }

    return map.get(head);
}

5. Palindrome Check

function isPalindrome(head) {
    if (!head || !head.next) return true;

    // Find middle
    const middle = findMiddle(head);

    // Reverse second half
    let secondHalf = reverseList(middle);
    let firstHalf = head;

    // Compare
    while (secondHalf) {
        if (firstHalf.val !== secondHalf.val) {
            return false;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

---

Doubly Linked List Operations

Complete Doubly Linked List Implementation

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    insertFront(val) {
        const newNode = new DoublyListNode(val);

        if (!this.head) {
            this.head = this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }

        this.size++;
    }

    insertRear(val) {
        const newNode = new DoublyListNode(val);

        if (!this.tail) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }

        this.size++;
    }

    deleteFront() {
        if (!this.head) return null;

        const val = this.head.val;

        if (this.head === this.tail) {
            this.head = this.tail = null;
        } else {
            this.head = this.head.next;
            this.head.prev = null;
        }

        this.size--;
        return val;
    }

    deleteRear() {
        if (!this.tail) return null;

        const val = this.tail.val;

        if (this.head === this.tail) {
            this.head = this.tail = null;
        } else {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }

        this.size--;
        return val;
    }
}

---

Usage Examples

Here's how to use these techniques:

console.log("=== Linked List Techniques Demo ===");

// Create sample lists
const list1 = createLinkedList([1, 2, 3, 4, 5]);
const list2 = createLinkedList([2, 4, 6]);

console.log("Original list:", printList(list1));
console.log("Find middle:", findMiddle(list1).val);
console.log("3rd from end:", nthFromEnd(list1, 3).val);

const reversed = reverseList(createLinkedList([1, 2, 3, 4, 5]));
console.log("Reversed list:", printList(reversed));

const merged = mergeTwoLists(createLinkedList([1, 3, 5]), createLinkedList([2, 4, 6]));
console.log("Merged sorted lists:", printList(merged));

const sorted = sortList(createLinkedList([4, 2, 1, 3]));
console.log("Sorted list:", printList(sorted));

const palindromeList = createLinkedList([1, 2, 2, 1]);
console.log("Is palindrome:", isPalindrome(palindromeList));

// Doubly linked list demo
const dll = new DoublyLinkedList();
dll.insertFront(2);
dll.insertFront(1);
dll.insertRear(3);
console.log("DLL size:", dll.size);
console.log("Delete front:", dll.deleteFront());
console.log("Delete rear:", dll.deleteRear());

---

Time Complexity Summary

Operation	Time Complexity	Space Complexity
Traversal	O(n)	O(1)
Search	O(n)	O(1)
Insert at Beginning	O(1)	O(1)
Insert at End	O(n)	O(1)
Insert at Position	O(n)	O(1)
Delete	O(n)	O(1)
Reverse	O(n)	O(1)
Find Middle	O(n)	O(1)
Detect Cycle	O(n)	O(1)
Merge Two Lists	O(n + m)	O(1)
Merge K Lists	O(n log k)	O(log k)
Sort List	O(n log n)	O(log n)

---

Common Patterns to Remember

1. Dummy Node Pattern

Use a dummy node to simplify edge cases:

const dummy = new ListNode(0);
dummy.next = head;

2. Two Pointer Pattern

• Fast/Slow: Finding middle, cycle detection
• Gap Method: Nth from end problems

3. Previous Pointer Pattern

Keep track of previous node for deletions:

let prev = null;
let current = head;

4. Recursive Pattern

Many operations can be solved recursively:

• Reversal
• Merging
• Tree-like problems

5. Hash Map Pattern

For problems involving random pointers or complex references

---

Key Interview Tips

1. Always check for null: Handle empty lists gracefully
2. Use dummy nodes: Simplifies insertion/deletion at head
3. Draw diagrams: Visualize pointer manipulations
4. Test with examples: Use [1,2,3], [1], and [] as test cases
5. Consider edge cases: Single node, empty list, cycles

This comprehensive guide covers all essential linked list techniques for coding interviews and competitive programming!